1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include <cstdio>
#include <cstring>
#define LL long long
const int maxn = 1e4 + 5;
using namespace std;
int n, a[maxn], b[maxn], cnt[2][maxn << 1];
LL ans = 0, tmp;
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= n; i++){
tmp = 0; memset(cnt, 0, sizeof cnt);
for (int j = 1; j <= n; j++){
if (i == j) b[j] = 0;
else if (a[j] > a[i]) b[j] = 1;
else b[j] = -1;
}
for (int j = 1; j <= n; j++) b[j] += b[j - 1];
for (int j = 0; j < i; j++) cnt[0][b[j] + 10000] += (j + 1);
for (int j = i; j <= n; j++)
tmp += 1ll * cnt[0][b[j] + 10000] * j;
ans += 1ll * tmp * a[i];
}
printf("%lld\n", ans);
return 0;
}
|